The present invention relates generally to a data processing system and more particularly to a field compositor, a data processing circuit for merging fields of data.
As shown in FIG. 1, a field compositor selects a field F in a word B and merges the selected field F into a word A to compose a word C.
Various devices have been used as field compositors. FIG. 2 depicts the function of a prior art device which requires an intermediate storage element I with at least the size of the selected field F. The field F selected from a word B is temporarily stored in the intermediate storage element I. Then, the selected field F is merged into the word A to form the word C. As the sizes of the word A and the selected field F increase, the complexity of the circuitry increases significantly because of the need for routing the data from the word B to the intermediate storage element I and then from the intermediate storage element I and the word A to the word C. A larger selected field F also requires extra storage space for the intermediate storage element I.
Another prior art method implementing a field compositor requires an intermediate storage element having the same size as the composed word. The intermediate storage element stores a pre-determined binary word where the locations of the 1s (ones) define the field selected from the first word to be merged with the second word. FIG. 3 illustrates the method. The pre-determined word I is ANDed with the first word A while the complement of the pre-determined word is ANDed with the second word B. The results of the two ANDed operations are ORed together to form the combined word C. Again as the size of the combined word C increases, not only does the pre-determined word I require extra storage space, but also the complexity of the circuitry increases significantly due to the need for generating the pre-determined word and routing the pre-determined word and its complement to different locations to form the combined word.
Various devices that can be used as field compositors have been known for a number of years, and by way of example, several forms of such devices can be found in the following U.S. Patents.
U.S. Pat. No. 4,903,228, by D. G. Gregoire et al., entitled "Single Cycle Merge/Logic Unit" discloses a merge operation within a single machine cycle with an intermediate storage element.
U.S. Pat. No. 4,520,439, by A. E. Liepa, entitled "Variable Field Partial Write Data merge" discloses a writing operation where the length of the selected field to be written could vary from a single bit to the extent of writing a full memory word. The operation uses a pre-determined word to protect the bit positions that are not included in the selected field.
U.S. Pat. No. 4,569,016, by H. T. Hao et al., entitled "Mechanism For Implementing One Machine Cycle Executable Mask And Rotate Instructions In A Primitive Instruction Set Computing System" discloses performing a multitude of computer operations including rotating, masking and merging within one machine cycle by ring shifting under the control of a pre-determined word.
U.S. Pat. No. 3,906,459, by D. J. Desmonds et al., entitled "Binary Data Manipulation Network Having Multiple Function Capability For Computers" discloses a network to manipulate binary data using word pre-determination and merge operations to combine two operands.
U.S. Pat. No. 4,760,517, by M. J. Miller et al., entitled "Thirty-Two Bit, Bit Slice Processor" discloses a 32-bit processor executing single cycle complex operations such as merging data with a pre-determined word generator.
Field compositors have been used for genetic algorithm machines. A general discussion of Genetic Algorithms can be found in Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning.
There is a need for a field compositor that can merge words without the need for generating and storing any pre-determined word that depends on the size of the selected field F to be merged or the size of the combined word itself. There is also a need for a field compositor that can be implemented in a systematic and orderly fashion using a regular structure so that as the size of the compositor increases, the complexity of the circuit will not increase correspondingly.